package _dp

import org.junit.Assert
import org.junit.Test


/*
https://leetcode.cn/problems/unique-paths-ii/description/

63. 不同路径 II
给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角（即 grid[0][0]）。机器人尝试移动到 右下角（即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。
网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。
返回机器人能够到达右下角的不同路径数量。
测试用例保证答案小于等于 2 * 109。

示例 1：
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2

示例 2：
输入：obstacleGrid = [[0,1],[0,0]]
输出：1
 */
class leetcode_63_Kotlin {
    @Test
    fun test_1() {
        val actual = uniquePathsWithObstacles(
            arrayOf(
                intArrayOf(0, 0, 0), intArrayOf(0, 1, 0), intArrayOf(0, 0, 0)
            )
        )
        val expect = 2
        Assert.assertEquals(expect.toLong(), actual.toLong())
    }

    @Test
    fun test_2() {
        val actual = uniquePathsWithObstacles(
            arrayOf(
                intArrayOf(0, 1), intArrayOf(0, 0)
            )
        )
        val expect = 1
        Assert.assertEquals(expect.toLong(), actual.toLong())
    }

    @Test
    fun test_3() {
        val actual = uniquePathsWithObstacles(
            arrayOf(
                intArrayOf(0, 1, 0, 0)
            )
        )
        val expect = 0
        Assert.assertEquals(expect.toLong(), actual.toLong())
    }

    private fun uniquePathsWithObstacles(obstacleGrid: Array<IntArray>): Int {
        // print m * n 数组
        for (row in obstacleGrid) {
            println(row.contentToString())
        }

        // 1 确定数组以及下标

        // m 行 n 列
        val m = obstacleGrid.size
        val n = obstacleGrid[0].size
        // 若开始和结束位置有障碍物，则直接结束
        if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) {
            return 0
        }
//        println("${obstacleGrid[0][0]},${obstacleGrid[m - 1][n - 1]}")

        // 定义数组
        val dp: Array<Array<Int>> = Array(m) {
            Array(n) {
                0
            }
        }

        // println("dp:")
        //  for(row in  dp){
        //     println(row.contentToString())
        // }

        // 2 确定递推公式
        // 3 初始化数组
        // 初始化第1列
        for (i in 0 until m) {
            // TODO:同一列，有一个障碍物则停止初始化
            if (obstacleGrid[i][0] == 1){
                break
            }
            dp[i][0] = 1
        }
//        println("dp:")
//        for(row in  dp){
//            println(row.contentToString())
//        }

        // 初始化第1行
        for (j in 0 until n) {
            // TODO:同一行，有一个障碍物则停止初始化
            if (obstacleGrid[0][j] == 1) {
                break
            }
            dp[0][j] = 1
        }

        println("dp:")
        for(row in  dp){
            println(row.contentToString())
        }

//         println("dp:")
//         for(row in  dp){
//             println(row.contentToString())
//         }

        // 4 遍历顺序
        for (i in 1 until m) {
            for (j in 1 until n) {
                // 有障碍物，则跳过
                if (obstacleGrid[i][j] != 1) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
                }
            }
        }
        // 5 打印数组
        return dp[m - 1][n - 1]
    }
}